package codingPractice.xiaoHongShu;

import java.util.Arrays;
import java.util.Scanner;

/*
    n个座位围成一个环，m个学生选座位，一个座位坐一个人。
    老师将礼物放在一个座位上，如何选择，使得礼物到每个同学的距离之和最小。
 */

public class Test3 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()) {
            int n = sc.nextInt();
            int m = sc.nextInt();
            int[] arr = new int[m];
            for(int i=0;i<m;i++) {
                arr[i] = sc.nextInt();
            }

            int result = findOptimalSeat(n, m, arr);
            System.out.println(result);
        }
    }

    public static int findOptimalSeat(int n, int m, int[] students) {
        Arrays.sort(students);

        int[] prefixSum = new int[m+1];
        for(int i=1;i<=m;i++) {
            prefixSum[i] = prefixSum[i-1] + students[i-1];
        }

        int minDistance = Integer.MAX_VALUE;
        int optimalSeat = -1;

        for(int seat=1;seat<=n;seat++) {
            int totalDistance = 0;
            for(int student : students) {
                int clockwiseDistance = Math.abs(student - seat);
                int counterClockwiseDistance = n - clockwiseDistance;
                totalDistance += Math.min(clockwiseDistance, counterClockwiseDistance);
            }

            if(totalDistance < minDistance) {
                minDistance = totalDistance;
                optimalSeat = seat;
            }
        }

        return optimalSeat;
    }
}
